10.6. Birleşmeli Sıralama (Merge Sort)

Birleşmeli sıralama böl ve yönet yaklaşımına dayanır ve dolayısıyla rekürsif (özyinelemeli) tasarlanması doğasına uygundur. Sıralanması istenen küme elemanları, önce, iki alt kümeye parçalanır ve fonksiyon kendisini sol alt küme ve sağ alt küme için iki kez çağırır. Parçalama işlemine, alt kümelerdeki eleman sayısı bir tane olana kadar devam edilir. Alt kümelerde bir tane eleman kalmışsa rekürsif çağırmalar geriye doğru, çağırana, dönmeye başlar ve geri dönülürken alt kümeler elemanları sıralı olacak biçimde birleştirilir. Algoritma, adını, bu birleştirme işleminden almıştır. Aşağıda birleşmeli sıralamanın kaba-kodu verilmiştir:

Yukarıdaki algoritmada, ilk önce sol indisin sağdan küçük olup olmadığı sınanmıştır; bu koşul alt dizide birden çok eleman varsa olumlu çıkacağından aşağısındaki dört satırda verilen kodlar yürütülür. Bu koşul sağlanmazsa alt dizide bir eleman var anlamına gelir ve birşey yapılmadan çağırana geri dönülür. Görüldüğü gibi dizi üzerinde birden çok eleman varsa ilk yapılan k=(sol+sag)/2 işlemiyle orta elemanın indisi hesaplanmakta ve fonksiyon alt parçalar için - kendisini iki kez çağırmaktadır. Buraya kadar bölme işlemleri yapılmış oldu. Son satırda ise, ki bu satır rekürsif fonksiyonların geri dönüşünde yürütülür, kısmi sıralanmış alt dizilerin birleştirilmesi yapılır.